/*
ID: icerupt1
PROG: bigbrn
LANG: C++11
*/

/* solution
 *
 * 很水的dp。
 * 
*/
#include <fstream>
#include <iostream>

std::ifstream fin {"bigbrn.in" };
std::ofstream fout{"bigbrn.out"};

int const maxn = 1002;
bool tree[maxn][maxn];
int max_up[maxn][maxn];
int max_left[maxn][maxn];
int max_s[maxn][maxn];
int n, m;

int main()
{
	fin >> n >> m;
	for (int i = 0, x, y; i < m; i++) {
		fin >> x >> y;
		tree[x][y] = true;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (!tree[i][j]) {
				max_up[i][j] = max_up[i-1][j] + 1;
				max_left[i][j] = max_left[i][j-1] + 1;
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (!tree[i][j]) {
				max_s[i][j] = std::min(max_s[i-1][j-1] + 1,
						std::min(max_up[i][j], max_left[i][j]));
				ans = std::max(ans, max_s[i][j]);
			}
		}

	std::cout << ans << '\n';
	fout << ans << '\n';
}

